home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / b_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.7 KB  |  92 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  b_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef BHEAPH
  19. #define BHEAPH
  20.  
  21. #include <LEDA/basic.h>
  22. #include <LEDA/list.h>
  23. #include <LEDA/array.h>
  24.  
  25. //------------------------------------------------------------------------------
  26. // b_heap: bounded heaps with keys from [a..b]
  27. //
  28. // Stefan Naeher  (1989)
  29. //------------------------------------------------------------------------------
  30.  
  31. class b_heap_node {
  32.  
  33. friend class b_heap;
  34. friend void print_b_heap_item(b_heap_node*);
  35.  
  36. int key;
  37. ent info;
  38. list_item loc;
  39.  
  40. b_heap_node(int k, ent i ) 
  41. { 
  42.   key = k; info = i; loc = 0; }
  43.  
  44.  OPERATOR_NEW(3)
  45.  OPERATOR_DEL(3)
  46.  
  47. };
  48.  
  49. typedef b_heap_node* b_heap_item;
  50. declare(list,b_heap_item)
  51.  
  52. typedef list(b_heap_item)* b_heap_bucket;
  53.  
  54. declare(array,b_heap_bucket)
  55.  
  56. class b_heap {
  57.  
  58.     int min;
  59.     int max;
  60.     int low;
  61.     int high;
  62.     
  63.     array(b_heap_bucket)  T;
  64.  
  65.  
  66. public:
  67.  
  68. b_heap(int a, int b);
  69. ~b_heap() { clear(); }
  70. b_heap_item insert(int key, ent info) ;
  71.  
  72. b_heap_item find_min();
  73. b_heap_item find_max();
  74. ent del_min();
  75. ent del_max();
  76. b_heap_item decrease_key(b_heap_item it, int k);
  77. b_heap_item increase_key(b_heap_item it, int k);
  78.  
  79. void delete_item(b_heap_item it);
  80. void clear();
  81.  
  82. ent info(b_heap_item it) { return it->info; }
  83. int key(b_heap_item it)  { return it->key; }
  84. int empty()              { return (find_min()==0) ? true : false; }
  85.  
  86. void print();
  87.  
  88. };
  89.  
  90. #endif
  91.  
  92.